class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int>& array) {
        if(array.size() == 0)
            return 0;
            
        vector<int> dp(array.size(), 0);
        dp[0] = array[0];

        int maxNum = dp[0];
        for(int i = 1; i < array.size(); ++i)
        {
            dp[i] = max(array[i], array[i]+dp[i-1]);
            maxNum = max(maxNum, dp[i]);
        }

        return maxNum;
    }
};

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    int sum = 0;

    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }

    int dfs(TreeNode* node, int pathSum)
    {
        if(node == nullptr)
        {
            return 0;
        }

        pathSum = pathSum * 10 + node->val;

        if(node->left == nullptr && node->right == nullptr)
            return pathSum;

        return dfs(node->left, pathSum) + dfs(node->right, pathSum);
    }
};
